#pragma once
#include<vector>
#include<iostream>
using namespace std;


class UnionFindSet
{
public:
	UnionFindSet(size_t size) :_ufs(size, -1)
	{

	}
	int FindRoot(int x)
	{
		int tmp = x;
		while (_ufs[tmp] >= 0)
		{
			tmp = _ufs[tmp];
		}
		return tmp;
	}
	void Union(int x1, int x2)
	{
		int r1 = FindRoot(x1);
		int r2 = FindRoot(x2);
		if (r1 != r2)
		{
			_ufs[r1] += _ufs[r2];
			_ufs[r2] = r1;
		}
	}
	int SetCount()
	{
		int cnt = 0;
		for (auto x : _ufs)
		{
			if (x < 0)
				cnt++;
		}
		return cnt;
	}
private:
	vector<int> _ufs;
};

void TestUFS()
{
	UnionFindSet u(10);

	u.Union(0, 6);
	u.Union(7, 6);
	u.Union(7, 8);

	u.Union(1, 4);
	u.Union(4, 9);

	u.Union(2, 3);
	u.Union(2, 5);

	cout << u.SetCount() << endl;
}